#include <iostream>

using namespace std;
// 对一个栈，添加Getbottom()运算用于直接返回栈底元素
// 使用带尾结点rear指针的循环单链表实现链栈
template <typename T>
struct LinkNode // 链栈结点类型
{
    T data;     // 数据域
    LinkNode* next; // 指针域
    LinkNode():next(nullptr) {} // 构造函数
    LinkNode(T d):data(d),next(nullptr){}   // 重载构造函数
};

template <typename T>
class STACK     // 链栈类模板
{
private:
    LinkNode<T>* rear;      // 链栈尾结点指针
public:
    STACK():rear(nullptr){} //构造函数
    ~STACK()        // 析构函数
    {
        if(rear == nullptr) return; // 空链表直接返回
        LinkNode<T>* pre = rear, *p = pre->next;
        while(p != rear)
        {
            delete pre;
            pre = p;
            p = p->next;    // pre，p同步后移
        }
        delete pre;
    }
    bool empty()    // 判断栈空
    {
        return rear == nullptr;
    }
    bool push(T e)  // 进栈算法
    {
        auto *p = new LinkNode<T>(e);    // 新建节点p
        if(empty()) // 栈为空的情况
        {
            rear = p;
            rear->next = rear;
        }
        else                        // 栈不空的情况
        {
            p->next = rear->next;   // 将结点p插入到结点rear之后
            rear->next = p;
        }
        return true;
    }
    bool pop(T& e)      // 出栈算法
    {
        if(empty()) return false;   // 栈空的情况

        LinkNode<T>* p;     // 指向要删除结点
        if(rear->next == rear)  // 栈中只有一个结点的情况
        {
            p = rear;
            rear = nullptr;
        }
        else                    // 栈中有2个及以上的结点的情况
        {
            p = rear->next;
            rear->next = p->next;
        }
        e = p->data;
        delete p;   // 释放结点p
        return true;
    }
    bool gettop(T& e)   // 取栈顶元素
    {
        if(empty()) return false;   // 栈空的情况
        e = rear->next->data;
        return true;
    }
    // 取栈底元素
    T Getbottom()
    {
        if(empty()) throw "栈空";
        return rear->data;
    }
};

int main() {
    int e;
    STACK<int> st;
    cout << "push 1...5 into stack" << endl;
    for(int i = 1; i <= 5; i++)
        st.push(i);
    cout << "Getbottom(): " << st.Getbottom() << endl;  // 1
    st.pop(e);
    cout << "pop(): " << e << endl;   // 5
    st.pop(e);
    cout << "pop(): " << e << endl;   // 4
    cout << "Getbottom(): " << st.Getbottom() << endl; // 1
    return 0;
}
